package com.hanxiaozhang.heap;

/**
 * 〈一句话功能简述〉<br>
 * 〈大根堆〉
 *
 * @author hanxinghua
 * @create 2021/9/14
 * @since 1.0.0
 */
public class MaxHeap {

    public static void main(String[] args) {
        int x = 0 - 1 / 2;
        int y = 0 - 1 % 2;
        System.out.println(x);
        System.out.println(y);
        x = -2 / 2;
        y = -2 % 2;
        System.out.println(x);
        System.out.println(y);
        System.out.println("------------");

        MaxHeap myMaxHeap =new MaxHeap(10);
        myMaxHeap.push(7);
        myMaxHeap.push(10);
        myMaxHeap.push(2);
        myMaxHeap.push(12);
        myMaxHeap.push(3);
        System.out.println(myMaxHeap.pop());
        System.out.println(myMaxHeap.pop());


    }

    /**
     * 数组,存放堆信息
     *
     */
    private int[] heap;

    /**
     * 堆的容量
     */
    private final int capacity;

    /**
     * 最大堆的大小
     */
    private int heapSize;


    public MaxHeap(int capacity) {
        heap = new int[capacity];
        this.capacity = capacity;
        heapSize = 0;
    }

    public boolean isEmpty() {
        return heapSize == 0;
    }

    public boolean isFull() {
        return heapSize == capacity;
    }

    /**
     * 添加
     *
     * @param value
     */
    public void push(int value) {
        if (heapSize == capacity) {
            throw new RuntimeException("heap is full");
        }
        heap[heapSize] = value;
        heapInsert(heap, heapSize++);
    }

    /**
     * 返回最大值，并且删除，并且剩下的数还是最大堆
     *
     * 弹出
     *
     * @return
     */
    public int pop() {
        int ans = heap[0];
        // i. heapSize减一
        // ii. heapSize减一位置与0交换
        swap(heap, 0, --heapSize);
        heapify(heap, 0, heapSize);
        return ans;
    }

    /**
     * 插入堆，调整堆的结构
     * 停止条件：i.父节点元素值比节点元素值的大。ii.或者节点没有父节点，即节点索引是0
     *
     * @param arr
     * @param index
     */
    private void heapInsert(int[] arr, int index) {

        // 节点比父节点值大，交换
        while (arr[index] > arr[(index - 1) / 2]) {
            swap(arr, index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }

    /**
     * 作用：堆化，将整个数组构建成一个堆。
     *
     * 从index位置往下看，不断下沉。
     * 停止条件：i.我的孩子都不我大了。ii.或者我没有孩子了。
     *
     * @param arr
     * @param index
     * @param heapSize  堆的大小
     */
    private void heapify(int[] arr, int index, int heapSize) {
        int left = index * 2 + 1;
        // 左孩子越界，右孩子必越界，即left < heapSize 代表我有孩子
        while (left < heapSize) {
            //  left + 1 < heapSize ==> 右节点索引 <  heapSize
            //  arr[left + 1] > arr[left] ==> 右节点元素大于左节点元素
            //  largest ==> 当前节点的孩子节点中最大的节点索引位置
            int largest = (left + 1 < heapSize && arr[left + 1] > arr[left]) ? left + 1 : left;
            //  largest与当前节点索引比较
            largest = arr[largest] > arr[index] ? largest : index;
            //  相同 break
            if (largest == index) {
                break;
            }
            // 不同交换
            swap(arr, largest, index);
            // 下沉，寻找下一层
            index = largest;
            left = index * 2 + 1;
        }
    }

    /**
     * 交换
     *
     * @param arr
     * @param i
     * @param j
     */
    private void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}
